class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int n = s.size();
        vector<int> next(n);
        int i = 1, j = 0;
        for (; i < n; ++i) { // 算next数组
            while (j > 0 && s[i] != s[j]) j = next[j - 1];
            if (s[i] == s[j]) ++j;
            next[i] = j;
        }
        // 最后一个字符的最长前后缀 不为0 且 总长度为基准重复子串长度的倍数
        return next[n - 1] != 0 && n % (n - next[n - 1]) == 0;
    }
};